package com.agile.leetcode.array.swingqueue;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author ChenZhangKun
 * @Date 2020/5/28 9:56
 */

/**
 * 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
 *
 * 例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
 *
 * 给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/wiggle-subsequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
@SuppressWarnings("all")
public class SwingQueue {
    public static void main(String[] args) {
        int[] array={1,7,4,9,2,5};
        int i = swingQueue(array);
        System.out.println(i);
        int i1 = new Solution3().wiggleMaxLength(new int[]{1,17,5,10,13,15,10,5,16,8});
        System.out.println(i1);
    }
    public static int swingQueue(int[] array){
        int len=array.length;
        List<Integer> list=new ArrayList<>();
        // 判断是否为摆动
        for (int i = 0; i <len-1 ; i++) {
              int j=i+1;
                if (array[j]-array[i]>0){
                    list.add(1);
                }else {
                    list.add(-1);
                }

        }
        for (int i = 0; i <list.size()-1 ; i++) {
            if (list.get(i)*(-1)==list.get(i+1)){
                if (i==list.size()-2){
                    return len;
                }
                continue;
            } else {
                break;
            }
        }
        // 原数组非摆动数列 从大到小

//        for (int i = array.com.agile.leetcode.array.length-1; i >0 ; i--) {
//            int j=array.com.agile.leetcode.array.length-i;
//            for (int k = 0; k <list.size() ; k++) {
//                Integer remove = list.remove(k);
//                Integer[] ints=new Integer[list.size()];
//                Integer[] integers = list.toArray(ints);
//                boolean swim = isSwim(integers);
//                if (swim){
//                    return list.size();
//                }else {
//                    list.add(k,remove);
//                }
//            }
  //      }
        //
        for (int i = 0; i <list.size() ; i++) {
            Integer integer=list.remove(i);
            if (isSwim(list.toArray(new Integer[list.size()]))){
                return len-1;
            }else {
                list.add(i,integer);
            }

        }


        return -1;
    }
    // 判断是否为摆动数组
    public static boolean isSwim(Integer[] array){
        int len=array.length;
        List<Integer> list=new ArrayList<>();
        // 判断是否为摆动
        for (int i = 0; i <len-1 ; i++) {
            int j=i+1;
            if (array[j]-array[i]>0){
                list.add(1);
            }else {
                list.add(-1);
            }

        }
        for (int i = 0; i <list.size()-1 ; i++) {
            if (list.get(i)*(-1)==list.get(i+1)){
                if (i==list.size()-2){
                    return true;
                }
                continue;
            } else {
                break;
            }
        }
        return false;
    }
}
// g官方解法
// 暴力
class Solution {
    private int calculate(int[] nums, int index, boolean isUp) {
        int maxcount = 0;
        for (int i = index + 1; i < nums.length; i++) {
            if ((isUp && nums[i] > nums[index]) || (!isUp && nums[i] < nums[index]))
                maxcount = Math.max(maxcount, 1 + calculate(nums, i, !isUp));
        }
        return maxcount;
    }

    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2)
            return nums.length;
        return 1 + Math.max(calculate(nums, 0, true), calculate(nums, 0, false));
    }
}
// 动态规划
class Solution1 {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2)
            return nums.length;
        int[] up = new int[nums.length];
        int[] down = new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            for(int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    up[i] = Math.max(up[i],down[j] + 1);
                } else if (nums[i] < nums[j]) {
                    down[i] = Math.max(down[i],up[j] + 1);
                }
            }
        }
        return 1 + Math.max(down[nums.length - 1], up[nums.length - 1]);
    }
}
// 线性动态规划
 class Solution2 {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2)
            return nums.length;
        int[] up = new int[nums.length];
        int[] down = new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            for(int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    up[i] = Math.max(up[i],down[j] + 1);
                } else if (nums[i] < nums[j]) {
                    down[i] = Math.max(down[i],up[j] + 1);
                }
            }
        }
        return 1 + Math.max(down[nums.length - 1], up[nums.length - 1]);
    }
}
// 空间优化动态规划
class Solution3 {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2)
            return nums.length;
        int down = 1, up = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1])
                up = down + 1;
            else if (nums[i] < nums[i - 1])
                down = up + 1;
        }
        return Math.max(down, up);
    }
}
// 贪心算法
 class Solution4 {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2)
            return nums.length;
        int prevdiff = nums[1] - nums[0];
        int count = prevdiff != 0 ? 2 : 1;
        for (int i = 2; i < nums.length; i++) {
            int diff = nums[i] - nums[i - 1];
            if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
                count++;
                prevdiff = diff;
            }
        }
        return count;
    }
}




